package it.uniroma2.util.tree;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TreeDecomposition {
	
	public List<Tree> getSubtrees(Tree tree) throws Exception {
		ArrayList<Tree> treeList = new ArrayList<Tree>(); 
		getSubtrees(tree, treeList);
		return treeList;
	}
	
	private List<Tree> getSubtrees(Tree tree, List<Tree> fullList) {
		ArrayList<Tree> list = new ArrayList<Tree>();
		Tree rootNode = tree.cloneNode();
		if (tree.getChildren().size() > 0) {
			List<List<Tree>> childTrees = new ArrayList<List<Tree>>();
			for (Tree child : tree.getChildren()) {
				childTrees.add(getSubtrees(child, fullList));
			}
			list.addAll(appendTrees(tree, childTrees));
		}
		fullList.addAll(list);
		list.add(rootNode);
		return list;
	}
	
	private List<Tree> appendTrees(Tree rootNode, List<List<Tree>> childAlternatives) {
		ArrayList<Tree> results = new ArrayList<Tree>();
		int[] maxIndices = new int[childAlternatives.size()];
		for (int i=0; i<maxIndices.length; i++)
			maxIndices[i] = childAlternatives.get(i).size();
		int[] indices = nextCombination(null, maxIndices);
		while (indices != null) {
			Tree tree = rootNode.cloneNode();
			for (int i=0; i<indices.length; i++)
			tree.getChildren().add(childAlternatives.get(i).get(indices[i]));
			results.add(tree);
			indices = nextCombination(indices, maxIndices);
		}
		return results;
	}
	
	private int[] nextCombination(int[] oldIndices, int[] maxIndices) {
		int[] newIndices = oldIndices;
		if (oldIndices == null) {
			newIndices = new int[maxIndices.length];
			Arrays.fill(newIndices, 0);
		}
		else {
			int i;
			for (i=0; i<newIndices.length; i++) {
				newIndices[i]++;
				if (newIndices[i] == maxIndices[i])
					newIndices[i] = 0;
				else
					break;
			}
			if (i == newIndices.length)
				newIndices = null;
		}
		return newIndices;
	}
}
